﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.RegularExpressions
{
    public class Dfa
    {
        public DataStructures.Sets.ISet<int> States { get; private set; }
        public DataStructures.Sets.ISet<int> Finals { get; private set; }
        private readonly IMap<int, IMap<string,int>> _transitions;
        private readonly Func<IMap<string, int>> _createMapOfStrings;

        public Dfa(Func<DataStructures.Sets.ISet<int>> createSet = null,
                   Func<IMap<int, IMap<string, int>>> createMap = null,
                   Func<IMap<string,int>> createMapOfStrings = null )
        {
            createSet = createSet ?? (() => AlgoritmiaFactory.Sets<int>.Default);
            createMap = createMap ?? (() => AlgoritmiaFactory.Maps<int, IMap<string, int>>.Default);
            _createMapOfStrings = createMapOfStrings ?? (() => AlgoritmiaFactory.Maps<string, int>.Default);
            States = createSet();
            Finals = createSet();
            _transitions = createMap();
        }

        public int Start { get; set; }

        public void AddState(int q)
        {
            States.Add(q);
        }

        public void AddFinal(int q)
        {
            Finals.Add(q);
        }

        public void AddTransition(int tail, string symbol, int head)
        {
            if (! _transitions.Contains(tail))
            {
                _transitions[tail] = _createMapOfStrings();
            }
            _transitions[tail][symbol] = head;
        }

        public int? Destination(int q, string symbol)
        {
            if ( _transitions.Contains(q) && _transitions[q].Contains(symbol))
            {
                return _transitions[q][symbol];
            }
            return null;
        }

        public static Dfa BuildFromNfa(NFASet.Nfa nfa)
        {
            Func<IEnumerable<int>, IEnumerable<int>> closure = qs =>
                          {
                              var v = new HashSet<int>(qs);
                              var fifo = AlgoritmiaFactory.Fifos<int>.BuildDefault(qs);
                              while (fifo.Count > 0)
                              {
                                  var q = fifo.Pop();
                                  foreach (var q1 in nfa.Destinations(q, ""))
                                  {
                                      if (!v.Contains(q1))
                                      {
                                          v.Add(q1);
                                          fifo.Push(q1);
                                      }
                                  }
                              }
                              var it = v.ToList();
                              it.Sort();
                              return it;
                          };

            var trans = AlgoritmiaFactory.Maps<IEnumerable<int>, int>.Default;
            var states = closure(new[] {nfa.Start});
            var queue = AlgoritmiaFactory.Fifos<IEnumerable<int>>.Default;
            queue.Push( states);
            var dfa = new Dfa();
            var qi = trans[states] = trans.Count;
            dfa.AddState(qi);
            dfa.Start = qi;
            if ( states.Contains(nfa.End) )
            {
                dfa.AddFinal(qi);
            }
            while (queue.Count > 0)
            {
                var s = queue.Pop();
                var output = new HashSet<string>();
                foreach(var q in s)
                {
                    output.UnionWith(nfa.OutputSymbols(q));
                }
                foreach(var c in output)
                {
                    if ( !String.IsNullOrEmpty(c))
                    {
                        var newQFrom = new HashSet<int>();
                        foreach(var q in s)
                        {
                            newQFrom.UnionWith(nfa.Destinations(q,c));
                        }
                        var qq = closure(newQFrom);
                        if ( !trans.Keys().Any(k => k.SequenceEqual(qq)))
                        {
                            var dfaq = trans[qq] = trans.Count;
                            dfa.AddState(dfaq);
                            if (qq.Contains(nfa.End))
                            {
                                dfa.AddFinal(dfaq);
                            }
                            queue.Push(qq);
                        }
                        dfa.AddTransition(trans[s],c,trans[trans.Keys().Where(k => k.SequenceEqual(qq)).First()]);
                    }
                }
            }
            return dfa;
        }

    }
}
